1. Field of the Invention
The present invention relates to a semiconductor circuit having a cache memory, more specifically to a cache memory system for reducing times of replacing data between a cache memory and a main memory.
2. Prior Art
A cache memory system in the prior art is constituted as shown in FIG. 11.
A cache memory 100 is provided with a data array 102 storing the data, and is connected to a processor 130 and a main memory 106. Size of the data transferring between the data array 102 and the main memory 106 is determined at the design state, and according to this size, a memory access control means 111 transfers the data between the data array 102 and the main memory 106. Thus in the cache memory system in the prior art, the size of the data transferring between the main memory 106 and the cache memory 100 is fixed to any amount.
Operation of replacing the data between the main memory and the cache memory hereinafter is called replacing, and the size of the replaced data is called block-size.
If the block-size is fixed to any value, depending on characteristics of behavior of a program, times of replacing may be increased in two cases.
In one case, in comparison with amount of the data to be transferred from the main memory 106 to the cache memory 100, block-size which can be replaced in transfer of one time is small.
Then, times of transferring the data required by the processor from the main memory 106 to the cache memory 100 and times of transferring the data bit required by the processor from the cache memory 100 to the main memory 106 are increased.
Operation of transferring the data from the main memory to the cache memory is hereinafter called replacing-in, and operation of transferring the data from the cache memory to the main memory is called replacing-out.
In another case, in comparison with amount of the data to be transferred from the main memory 106 to the cache memory 100, block-size which can be replaced in transfer of one time is large. Then the data to be originally stored within the cache memory 100 may be replaced out together with the data to be replaced out from the cache memory 100 to the main memory 106.
Therefore regarding the data which are replaced out although to be originally stored within the cache memory 100, when the processor is going to refer the data, the data must be replaced in again.
In order to solve these problems, cache memories having constitution as disclosed in JP-A 62-118456 or JP-A 63-157249 have been proposed.
In any of cache memories, block-size is set to one predetermined value by instruction or the like, during initialization or during execution of program.
Thereby dealing with the difference of the scope within the spatial locality different in each program or the variation of the scope within the spatial locality during the execution of one program, the block-size can be varied.
In the computer system in the prior art, however, since a processor and a cache memory are separate LSIs, because of pin constraint of the LSI, width of a data bus between the processor and the cache memory can not be designed wide, and the block-size is designed large in comparison with the data bus width.
Since the block-size is designed large in comparison with the data bus width, there is a problem that the clock cycle number required for the data transfer is increased.
In order to solve these problems, a clock memory with variable line size has been proposed (Technical Report of the Information Processing Society of Japan, Architecture Research Group, ARC-119-28, August 1996).
This cache memory is based on that a processor, a cache memory and a DRAM being a main memory are merged on one LSI. Since the cache memory and the main memory are directly connected within the LSI, the cache memory is characterized in that the width of the data bus connecting between the cache memory and the main memory can be designed wide. Further the block-size can be set to one value predetermined as mode of the whole cache.
Therefore in a region where the block-size is small in comparison with the data bus width, the block-size can be set not increasing the cycle required for the data transfer.
In general, a cache memory is a storage device which utilizes property that the data once accessed can be accessed again within the near time at high possibility (time locality) and property that data in the vicinity of the accessed data can be soon accessed with high possibility (spatial locality), and stores the data to be referred by the processor in the near future with high possibility.
Noticing the spatial locality particularly, not only the scope within the spatial locality is different in each program, but also even in single program, the scope within the spatial locality is different depending on the address space.
This is clear considering an example that individual elements in two arrangements different in amount stored in address spaces separated from each other within certain time are accessed in the same times respectively. That is, comparing a wide address space storing a large arrangement and a narrow address space storing a small arrangement, it can be said that the former is high in the spatial locality.
However, since any of proposed architectures as above described, determines the block-size as mode of the whole cache uniquely, it is difficult to deal with the difference of the scope within the spatial locality in the address space.
If the set block-size is not suitable, the unnecessary replacing may be caused as above described.
Therefore the first problem to be solved by the present invention is to provide means for setting the block-size suitably in each address space in order to deal with the difference of the scope within the spatial locality in the address space, and to suppress the generating of the unnecessary replacing.
Further as the execution of the program advances, the referring frequency of the processor to the same address space varies.
As an example in this case, some data are frequently referred at some time, but are accessed rarely (or more frequently) as the execution of the program advances.
Therefore the second problem to be solved by the invention is, in order to deal with the difference of the scope within the spatial locality attendant on the execution of the program, in addition to the dealing with the first problem, to provide means for updating the block-size in each address space during the execution of the program thereby to suppress the generating of the unnecessary replacing.
In order to solve the first problem, in a cache memory system according to the present invention, a cache memory is provided for temporarily storing the data stored in a main memory, and a processor accesses the cache memory. The cache memory system is provided with a block-size information storing means for storing size of the data to be replaced between the cache memory and the main memory in every plural storage spaces of predetermined amount within the cache memory, and with means for replacing the data between the storage space in which a cache miss is occurred within the cache memory and the main memory, when the access of the processor to the storage space within the cache memory occurs a cache miss, at the block-size corresponding to the storage space in which the cache miss is occurred, among the size stored in the block-size information storing means.
In the cache memory system, access address outputted by the processor is provided with individual fields of tag address, index address, bank address and an offset within the bank, and the cache memory comprises at least two cache banks, and each cache bank as above described has a data array constituted by aggregate of elements storing the data in the word number assigned by the offset within the bank, a valid flag array constituted by aggregate of valid flags storing whether or not the data stored in the individual elements of the data array are valid, and a tag array storing the individual tag addresses of the data stored in the individual elements of the data arrays. The data array, the valid flag array and the tag array respectively output the data of the elements assigned by the index address, values of the valid flags of the data, and the tag addresses of the data. Further each cache bank as above described is provided with a comparator for comparing the tag address outputted by the tag array and the tag address within the access address and indicating the comparison result, when the value of the valid flag indicates the storing of the data valid to the element, with a first multiplexer for selecting and outputting the comparison result of the comparator of the cache bank assigned by the bank address, with the block-size information storing means for referring the size in each storage space within the cache memory at the index address, and with a memory access control circuit performing control of replacing the data between the cache memory and the main memory. When the processor outputs the access address, the memory access control circuit judges whether or not the cache miss is occurred by the output of the first multiplexer, and when the cache miss occurs, the memory access control circuit replaces the data between the storage space in which the cache miss is occurred and the main memory space assigned by the access address, at the block-size corresponding to the storage space in which the cache miss is occurred, among the size stored in the block-size information storing means.
In a cache memory system to solve the second problem, access address outputted by the processor is provided with individual fields of tag address, index address, bank address and an offset within the bank, and the cache memory comprises at least two cache banks, and each cache bank as above described has a data array constituted by aggregate of elements storing the data in the word number assigned by the offset within the bank, avalid flag array constituted by aggregate of valid flags storing whether or not the data stored in the individual elements of the data array are valid, a tag array storing the individual tag addresses of the data stored in the individual elements of the data array, and an access bit array constituted by aggregate of access bits storing whether or not the individual data stored in the individual elements of the data array are referred by the processor, after the data are read in the elements respectively until now. The data array, the valid flag array, the tag array and the access bit array respectively output the data of the elements assigned by the index address, values of the valid flags of the data, the tag addresses of the data, and values of the access bits of the data. Further each cache bank as above described is provided with a comparator for comparing the tag address outputted by the tag array and the tag address within the access address and outputting the comparison result, when the value of the valid flag indicates the storing of the data valid to the element, with a first multiplexer for selecting and outputting the comparison result of the comparator of the cache bank assigned by the bank address, with the block-size information storing means for outputting the size in each storage space within the cache memory assigned by the index address, with a line utility condition judging circuit for outputting a signal indicating the cache bank, if the comparison results outputted by the comparators of all cache banks and the values outputted by the access bits of all cache banks are inputted, when the comparison results are coincident and results are coincident and values of the outputted access bits indicate the referring by the processor, with a block-size determination circuit for determining the new size of the storage space, if the size of the storage space within the cache memory assigned by the index address, the bank address and the output of the line utility condition judging circuit are inputted, and with a memory access control circuit performing control of replacing the data between the cache memory and the main memory. When the processor outputs the access address, the memory access control circuit judges whether or not the cache miss is occurred by the output of the first multiplexer, and when the cache miss is occurred, the memory access control circuit replaces the data between the storage space in which the cache miss is occurred and the main memory space assigned by the access address, at the block-size corresponding to the storage in which the cache miss is occurred, among the size stored in the block-size information storing means, and the block-size determination circuit updates the size stored in the block-size information storing means.
The block-size information storing means has a second multiplexer for storing the size in each element within the cache memory and selecting and outputting the size of the cache bank assigned by the bank address, and when the cache miss is occurred, the memory access control circuit replaces the data between the space in which the cache miss is occurred and the main memory assigned by the access address, at the size outputted by the second multiplexer.
The block-size information storing means is provided with a second tag array storing the tag address of the data returned to the main memory and a table storing the size, and when the second tag array and the table are referred in the index address, the size and the tag address are outputted. A second comparator is provided for comparing the tag address outputted by the table and the tag address within the access address and outputting the comparison result, and a tag selection circuit is provided for selecting the tag address to be inputted to the table from outputs of the tag arrays of all cache banks by the bank address. When the cache miss is occurred, if the comparison result of the tag address of the access address by the second comparator and the tag address outputted by the second array are coincident, the data returned to the main memory are read into the cache memory again, at the size stored in the table assigned by the index address. The tag address selected in the tag selection circuit and the size assigned by the index address in which the cache miss is occurred and corresponding to the storage space within the cache memory are stored respectively in the second tag array and the table.